SherbyNet - /page/wikibook/entry.mu

Micron Document

`:top

In mathematics and computing, a `!triangular array`! of numbers, polynomials, or the like, is a doubly indexed sequence in which each row is only as long as the row's own index. That is, the `*i`*th row contains only `*i`* elements.

>>Contents

• `F0af`_`[Examples`#examples]`_`f

• `F0af`_`[Generalizations`#generalizations]`_`f

• `F0af`_`[Applications`#applications]`_`f

• `F0af`_`[Indexing`#indexing]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

• `F0af`_`[External links`#external-links]`_`f

-─

>>Examples

Notable particular examples include these:

• The `F33f`_`[Bell triangle`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bell_triangle]`_`f, whose numbers count the `F33f`_`[partitions of a set`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Partition_of_a_set]`_`f in which a given element is the largest `F33f`_`[singleton`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Singleton_(mathematics)]`_`f`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]

• `F33f`_`[Catalan's triangle`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Catalan's_triangle]`_`f, which counts strings of matched parentheses`:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]

• `F33f`_`[Euler's triangle`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Euler's_triangle]`_`f, which counts permutations with a given number of ascents`:cite-ref-3[`F5bf`_`[3`#cite-note-3]`_`f]

• `F33f`_`[Floyd's triangle`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Floyd's_triangle]`_`f, whose entries are all of the integers in order`:cite-ref-4[`F5bf`_`[4`#cite-note-4]`_`f]

• `F33f`_`[Hosoya's triangle`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Hosoya's_triangle]`_`f, based on the `F33f`_`[Fibonacci numbers`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Fibonacci_number]`_`f`:cite-ref-5[`F5bf`_`[5`#cite-note-5]`_`f]

• `F33f`_`[Lozanić's triangle`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Lozanić's_triangle]`_`f, used in the mathematics of chemical compounds`:cite-ref-6[`F5bf`_`[6`#cite-note-6]`_`f]

• `F33f`_`[Narayana triangle`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Narayana_triangle]`_`f, counting strings of balanced parentheses with a given number of distinct nestings`:cite-ref-7[`F5bf`_`[7`#cite-note-7]`_`f]

• `F33f`_`[Pascal's triangle`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Pascal's_triangle]`_`f, whose entries are the `F33f`_`[binomial coefficients`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binomial_coefficients]`_`f`:cite-ref-8[`F5bf`_`[8`#cite-note-8]`_`f]

Triangular arrays of integers in which each row is symmetric and begins and ends with 1 are sometimes called `!generalized Pascal triangles`!; examples include Pascal's triangle, the Narayana numbers, and the triangle of Eulerian numbers.`:cite-ref-9[`F5bf`_`[9`#cite-note-9]`_`f]

>>Generalizations

Triangular arrays may list mathematical values other than numbers; for instance the `F33f`_`[Bell polynomials`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bell_polynomials]`_`f form a triangular array in which each array entry is a polynomial.`:cite-ref-10[`F5bf`_`[10`#cite-note-10]`_`f]

Arrays in which the length of each row grows as a linear function of the row number (rather than being equal to the row number) have also been considered.`:cite-ref-11[`F5bf`_`[11`#cite-note-11]`_`f]

>>Applications

`F33f`_`[Romberg's method`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Romberg's_method]`_`f can be used to estimate the value of a `F33f`_`[definite integral`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Definite_integral]`_`f by completing the values in a triangle of numbers.`:cite-ref-12[`F5bf`_`[12`#cite-note-12]`_`f]

The `F33f`_`[Boustrophedon transform`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Boustrophedon_transform]`_`f uses a triangular array to transform one `F33f`_`[integer sequence`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Integer_sequence]`_`f into another.`:cite-ref-13[`F5bf`_`[13`#cite-note-13]`_`f]

In general, a triangular array is used to store any table indexed by two `F33f`_`[natural numbers`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Natural_numbers]`_`f where `*j`* ≤ `*i`*.

>>Indexing

Storing a triangular array in a computer requires a mapping from the two-dimensional coordinates (`*i`*, `*j`*) to a linear `F33f`_`[memory address`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Memory_address]`_`f. If two triangular arrays of equal size are to be stored (such as in `F33f`_`[LU decomposition`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=LU_decomposition]`_`f), they can be combined into a standard `F33f`_`[rectangular array`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Array_(data_structure)]`_`f. If there is only one array, or it must be easily appended to, the array may be stored where row `*i`* begins at the `*i`*th `F33f`_`[triangular number`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Triangular_number]`_`f `*Ti`*. Just like a rectangular array, one multiplication is required to find the start of the row, but this multiplication is of two variables (`B100`F9d9i*(i+1)/2`f`b), so some optimizations such as using a `F33f`_`[sequence of shifts and adds`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Multiplication_algorithm]`_`f are not available.

>>See also

• `F33f`_`[Triangular number`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Triangular_number]`_`f, the number of entries in such an array up to some particular row

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citerefshallit1980`a`F33f`_`[Shallit, Jeffrey`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Jeffrey_Shallit]`_`f (1980), "A triangle for the Bell numbers" (PDF), in Hoggatt, Verner E. Jr.; Bicknell-Johnson, Marjorie (eds.), `*A collection of manuscripts related to the Fibonacci sequence`*, Santa Clara, Calif.: Fibonacci Association, pp. 69–71, `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 0624091.

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citerefkitaevliese2013`a`F33f`_`[Kitaev, Sergey`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Sergey_Kitaev]`_`f; Liese, Jeffrey (2013), "Harmonic numbers, Catalan's triangle and mesh patterns" (PDF), `*`F33f`_`[Discrete Mathematics`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Discrete_Mathematics_(journal)]`_`f`*, `!313`! (14): 1515–1531, `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:1209.6423, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/j.disc.2013.03.017, `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 3047390, `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 18248485.

`:cite-note-3`!3.`! `F0af`_`[↑`#cite-ref-3]`_`f `:citerefvellemancall1995`aVelleman, Daniel J.; Call, Gregory S. (1995), "Permutations and combination locks", `*Mathematics Magazine`*, `!68`! (4): 243–253, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1080/0025570X.1995.11996328, `F33f`_`[JSTOR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=JSTOR_(identifier)]`_`f 2690567, `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 1363707.

`:cite-note-4`!4.`! `F0af`_`[↑`#cite-ref-4]`_`f `:citerefmillermillerjackson1987`aMiller, Philip L.; Miller, Lee W.; Jackson, Purvis M. (1987), `*Programming by design: a first course in structured programming`*, Wadsworth Pub. Co., pp. 211–212, `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-0-534-08244-4.

`:cite-note-5`!5.`! `F0af`_`[↑`#cite-ref-5]`_`f `:citerefhosoya1976`a`F33f`_`[Hosoya, Haruo`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Haruo_Hosoya]`_`f (1976), "Fibonacci triangle", `*`F33f`_`[The Fibonacci Quarterly`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=The_Fibonacci_Quarterly]`_`f`*, `!14`! (2): 173–178, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1080/00150517.1976.12430575.

`:cite-note-6`!6.`! `F0af`_`[↑`#cite-ref-6]`_`f `:citereflosanitsch1897`a`F33f`_`[Losanitsch, Sima M.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Sima_Lozanić]`_`f (1897), "Die Isomerie-Arten bei den Homologen der Paraffin-Reihe" [The isomery species of the homologues of the paraffin series], `*`F33f`_`[Chem. Ber.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Chem._Ber.]`_`f`* (in German), `!30`! (2): 1917–1926, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1002/cber.189703002144.

`:cite-note-7`!7.`! `F0af`_`[↑`#cite-ref-7]`_`f `:citerefbarry2011`aBarry, Paul (2011), "On a generalization of the Narayana triangle" (PDF), `*Journal of Integer Sequences`*, `!14`! (4) 11.4.5, `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 2792161.

`:cite-note-8`!8.`! `F0af`_`[↑`#cite-ref-8]`_`f `:citerefedwards2002`a`F33f`_`[Edwards, A. W. F.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=A._W._F._Edwards]`_`f (2002), `*Pascal's Arithmetical Triangle: The Story of a Mathematical Idea`*, JHU Press, `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-0-8018-6946-4.

`:cite-note-9`!9.`! `F0af`_`[↑`#cite-ref-9]`_`f `:citerefbarry2006`aBarry, Paul (2006), "On integer-sequence-based constructions of generalized Pascal triangles" (PDF), `*Journal of Integer Sequences`*, `!9`! (2) 6.2.4, `F33f`_`[Bibcode`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Bibcode_(identifier)]`_`f:2006JIntS...9...24B.

`:cite-note-10`!10.`! `F0af`_`[↑`#cite-ref-10]`_`f `:citerefrota-bul-hancockazizpelillo2012`aRota Bulò, Samuel; Hancock, Edwin R.; Aziz, Furqan; Pelillo, Marcello (2012), "Efficient computation of Ihara coefficients using the Bell polynomial recursion", `*Linear Algebra and Its Applications`*, `!436`! (5): 1436–1441, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1016/j.laa.2011.08.017, `F33f`_`[MR`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MR_(identifier)]`_`f 2890929.

`:cite-note-11`!11.`! `F0af`_`[↑`#cite-ref-11]`_`f `:citereffielderalford1991`aFielder, Daniel C.; Alford, Cecil O. (1991), "Pascal's triangle: Top gun or just one of the gang?", in Bergum, Gerald E.; Philippou, Andreas N.; Horadam, A. F. (eds.), `*Applications of Fibonacci Numbers (Proceedings of the Fourth International Conference on Fibonacci Numbers and Their Applications, Wake Forest University, N.C., U.S.A., July 30–August 3, 1990)`*, Springer, pp. 77–90, `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 9780792313090.

`:cite-note-12`!12.`! `F0af`_`[↑`#cite-ref-12]`_`f `:citerefthacher-jr-1964`aThacher Jr., Henry C. (July 1964), "Remark on Algorithm 60: Romberg integration", `*Communications of the ACM`*, `!7`! (7): 420–421, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1145/364520.364542, `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 29898282.

`:cite-note-13`!13.`! `F0af`_`[↑`#cite-ref-13]`_`f `:citerefmillarsloaneyoung1996`aMillar, Jessica; Sloane, N. J. A.; Young, Neal E. (1996), "A new operation on sequences: the Boustrouphedon transform", `*Journal of Combinatorial Theory`*, Series A, `!76`! (1): 44–54, `F33f`_`[arXiv`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ArXiv_(identifier)]`_`f:math.CO/0205218, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1006/jcta.1996.0087, `F33f`_`[S2CID`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=S2CID_(identifier)]`_`f 15637402.

>>External links

• `:reference-mathworld-number-triangle`a`:citerefweisstein`a`F33f`_`[Weisstein, Eric W.`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Eric_W._Weisstein]`_`f, "Number Triangle", `*`F33f`_`[MathWorld`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=MathWorld]`_`f`*

`c`F0af`_`[↑ Back to top`#top]`_`f`a